package com.zz.util;

import com.zz.tree.TreeNode;

import java.util.ArrayList;
import java.util.List;

public class TreeNodeUtil {
    /**
     * 中序遍历
     * @param node
     */
    public static void inorderTraversal(TreeNode node){
        if(node == null){
            return;
        }
        System.out.print(node.val + "\t");
        inorderTraversal(node.left);
        inorderTraversal(node.right);
    }

    /**
     * 前序遍历
     * @param node
     */
    public static void preorderTraversal(TreeNode node){
        if(node == null){
            return;
        }
        preorderTraversal(node.left);
        System.out.print(node.val + "\t");
        preorderTraversal(node.right);
    }

    /**
     * 后序遍历
     * @param node
     */
    public static void postorderTraversal(TreeNode node){
        if(node == null){
            return;
        }
        postorderTraversal(node.left);
        postorderTraversal(node.right);
        System.out.print(node.val + "\t");
    }

    /**
     * 层序遍历
     * @param node
     */
    public static void orderTraversal(TreeNode node){
        if(node == null){
            return;
        }
        System.out.print(node.val + "\t");
        System.out.print(node.left.val + "\t");
        System.out.print(node.right.val + "\t");
    }

    public static List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> result = new ArrayList();
        if (root == null) {
            return result;
        }

        traverse(root, 0, result);
        return result;
    }

    public static void traverse(TreeNode node, int depth, List<List<Integer>> result) {
        if (node == null) {
            return;
        }

        // 如果当前深度的结果列表不存在，则创建一个新的列表
        if (depth >= result.size()) {
            result.add(new ArrayList());
        }

        // 将当前节点的值添加到对应深度的结果列表中
        result.get(depth).add(node.val);

        // 递归遍历左右子树
        traverse(node.left, depth + 1, result);
        traverse(node.right, depth + 1, result);
    }

}
